We show that finding an equilibrium in preference games is \textbf{PPAD}-hard.
We will follow the framework
of~\cite{DaskalakisGoldbergPapadimitriou06}, which shows that finding a
Nash equilibrium in a degree-3 graphical game is \textbf{PPAD}-hard, using a
reduction from the \textbf{PPAD}-complete problem \threeDBrouwer.  In this
problem, we are given a 3-D cube in which each dimension is broken
down into $2^{-n}$ segments -- thereby dividing the cube into $2^{3n}$
cubelets.  We are also given a circuit that takes as input the 3
coordinates of the center of a cubelet (each as an $n$-bit number) and
returns a 2-bit number that represents one of four 3-D vectors: either
$(1,0,0)$, $(0,1,0)$, $(0,0,1)$, or $(-1,-1,-1)$. A solution to the
\threeDBrouwer\ instance is a cubelet vertex such that the set of 8
results obtained by running the circuit on each of the 8 cubelets
surrounding the vertex contains each of the four vectors at least
once.

As in~\cite{DaskalakisGoldbergPapadimitriou06}, we will construct a set
of gadgets to simulate various arithmetic operators, logical
operators, arithmetic comparisons and other operators.  We then follow
their framework to systematically combine these gadgets to simulate
the input boolean circuit and to encode the geometric condition of
discrete fixed points in the \threeDBrouwer\ instance.  In the preference game we construct, we specify the preference relation of any player $P$ by
an ordered list of a subset of the players, with the last element
being $P$, also referred to as the ``self'' strategy.  When we say
that a player $P$ {\em plays itself}\/ with weight $v$, we mean that
$P$ assigns a weight of $v$ to strategy $P$.  We'll engineer the
payoffs such that the game is only in equilibrium if the weights
assigned by certain players to {\em themselves}\/ successfully echo
the inputs and outputs of 8 copies of the circuit that surround a
solution vertex of the \threeDBrouwer\ instance.  

For this reduction, we require the following sets of players.

\begin{enumerate}
\item One player for each of the 3 dimensions (the \emph{coordinate
players}). If the graph is an equilibrium, each coordinate player
plays itself with weight equal to its coordinate of the \threeDBrouwer\
solution vertex.

\item 
One player for each of the bits of each of the 3 coordinates (the
\emph{bit players}). In order to force these players to correctly
represent the bits, we need some additional players. Assuming we've
correctly calculated the first $i-1$ bits of coordinate $x$ (call them
$x_0, \ldots, x_{i-1}$), we can create the $i^{th}$ bit as
follows. One player will play itself with weight $p_i = x -
\sum_{j=0}^{i-1} \frac{x_j}{2^{j}}$. The bit player will play itself
with weight equal to the $i^{th}$ bit. If $p_i 
\geq \frac{1}{2^i}$, then this bit should be 1. Otherwise, it should
be 0. Therefore, in order to properly extract the bits, we create the
following four types of players.
\newcounter{saveenum}
\begin{enumerate}
\item HALF player: 
In any equilibrium in which a given player plays itself with weight
$a$, the HALF player will play itself with weight $\frac{a}{2}$.
\item DIFF player: 
In any equilibrium in which two given players play themselves
with weights $a$ and $b$, the DIFF player will play itself
with weight $a - b$.
\item VALUE player: 
In any equilibrium, the VALUE player plays itself with weight
$\frac{1}{2}$. This can be easily created by combining a player whose
first preference is itself with a HALF player.
\item LESS player: 
In any equilibrium in which two given players play themselves with
weights $a$ and $b$, respectively, the LESS player plays itself with
weight 1 iff $a \geq b$, and plays itself with weight 0 otherwise.
(Actually, the LESS player we create will be inaccurate if $a$ and $b$ are very close,
which we discuss more below.)
\setcounter{saveenum}{\value{enumii}}
\end{enumerate}
\item 
One player simulates each type of gate used in the circuit of the \threeDBrouwer\ instance. For this, we create 3 more types of players.
\begin{enumerate}
\setcounter{enumii}{\value{saveenum}} 
\item AND player: 
In any equilibrium in which two given players play themselves with
weights $a$ and $b$ $\in \{0,1\}$, the AND player will play itself with weight $a
\land b$.
\item OR player: 
In any equilibrium in which two given players play themselves with
weights $a$ and $b$ $\in \{0,1\}$, the OR player will play itself with weight $a
\lor b$.
\item NOT player: 
In any equilibrium in which a given player plays itself with weight
$a$ $\in \{0,1\}$, the NOT player will play itself with weight $\lnot a$.
\setcounter{saveenum}{\value{enumii}}
\end{enumerate}

\item 
Finally, we need to ensure that the graph is in equilibrium if and
only if all four vectors are represented in the results of the 8
circuits.  As in~\cite{DaskalakisGoldbergPapadimitriou06}, we will
represent the output of each circuit using 6-bits, one each for $+x,
-x, +y, -y, +z, -z$. Now, the 4 possible result vectors are
represented as $100000$, $001000$, $000010$, and $010101$. We can use
these circuit results with only two additional types of players to
feed back into the original coordinate players.  First, we will create
an OR player for each of the 6 bits (over the 8 vertices), which
yields a result of six 1's if and only if this is a solution vertex.
Therefore, one AND player for each coordinate will all return 1 if and
only if this is a solution vertex; at least one of the coordinates
will be 0 otherwise. We can turn this around using a NOT player for
each coordinate, so that we get all 0's if and only if this is a
solution vertex. Finally, we need the last two new player types, which
we'll use to add these results back to a copy of the original
coordinates (the result will be the original coordinate player).
\begin{enumerate}
\setcounter{enumii}{\value{saveenum}} 
\item 
COPY player: In any equilibrium in which a given player plays itself
with weight $a$, the COPY player will also play itself with weight
$a$.
\item 
SUM player: In any equilibrium in which two given players play
themselves with weights $a$ and $b$, the SUM player will play itself
with weight $\min(a + b, 1)$.
\end{enumerate}
If the coordinates represented a solution vertex to the \threeDBrouwer\
instance, then all the values we've added back in will be zero; so the
coordinate players cannot do better by changing their strategies.  On
the other hand, if the coordinates do not form a solution vertex, then
at least one of the values is 1, so that the coordinate player will
have incentive to change strategies and play more weight on itself.
\end{enumerate}


We now describe how to create the
new types of players (gadgets) required for the reduction. For each of
these gadget definitions, we assume we are given a preference game such
that in any equilibrium, player $X$ plays itself with weight $v_1$ and
player $Y$ plays itself with weight $v_2$.  For the first three gadgets,
we assume $v_1, v_2 \in \{0,1\}$. For the rest of the gadgets, we
assume $v_1, v_2 \in [0,1]$.
\smallskip

%\BfPara{$\mbox{OR}(X,Y)$}
\subsubsection*{$\mbox{OR}(X,Y)$}
We can add a new node $R = \mbox{OR}(X,Y)$ that will
play itself with weight $v_1 \lor v_2$ in any equilibrium.  Create a node $R_1$ with
preference list $(X, Y, R_1)$. Let node $R$'s preference list be
$(R_1, R)$.  Now, if $v_1$ and/or $v_2$ is 1, then $R_1$ will play
$R_1$ with weight 0, so $R$ will play itself with weight 1. If both
$v_1$ and $v_2$ is 0, then $R_1$ will play itself with weight 1, so
$R$ will play $R_1$ with weight 1 and $R$ with weight 0.

%\\
%\BfPara{$\mbox{NOT}(X)$}
\subsubsection*{$\mbox{NOT}(X)$}
We can add a new node $N = \mbox{NOT}(X)$ that will play itself with weight $\lnot v_1$ in any equilibrium.  Let node $N$'s preference
list be $(X, N)$.  Clearly, $N$ will play $X$ as much as $v_1$ and
will play $N$ with the remainder.
%\\ 
%\BfPara{$\mbox{AND}(X,Y)$}
\subsubsection*{$\mbox{AND}(X,Y)$}
We can add a new node $A
= \mbox{AND}(X,Y)$ that will play
itself with weight $v_1 \land v_2$ in any equilibrium.  Assemble the OR and NOT gadgets
$\mbox{NOT}(\mbox{OR}(\mbox{NOT}(X),\mbox{NOT}(Y)))$.
%\\
%\BfPara{$\mbox{SUM}(X,Y)$}
\subsubsection*{$\mbox{SUM}(X,Y)$}
We can add a new node
$S=\mbox{SUM}(X,Y)$ that will play
itself with weight $max(1, v_1 + v_2)$ in any equilibrium.  Create a node $S_1$ with
preference list $(X, Y, S_1)$. Let node $S$'s preference list be
$(S_1, S)$.  Now, clearly node $S_1$ will play $S_1$ with weight
$max(0, 1-v_1-v_2)$, and node $S$ will play $S_1$ that same
amount. So node $S$ will play itself with weight $1 - max(0,
1-v_1-v_2)$. In other words, if $v_1 + v_2
\geq 1$, then $S$ will play itself with weight 1. Otherwise,
$S$ will play itself with weight $1 - 1 + v_1 + v_2 = v_1 +
v_2$, as desired.
%\\ 
%\BfPara{$\mbox{DIFF}(X,Y)$}
\subsubsection*{$\mbox{DIFF}(X,Y)$}
We can add a new node $D
= \mbox{DIFF}(X,Y)$ that will play
itself with weight $v_1 - v_2$ if $v_1 > v_2$, or 0 otherwise in any equilibrium.  Create
a node $D_1$ with preference list $(X, D_1)$. $D_1$ will play itself
with weight $1-v_1$. Now set the preference list for $D$ to $(D_1,
Y, D)$. $D$ will play itself with weight $\min(0, 1 - (1-v_1) - v_2)
= \min(0, v_1 - v_2)$, as desired.
%\\ 
%\BfPara{$\mbox{COPY}(X)$}
\subsubsection*{$\mbox{COPY}(X)$}
We can add a new node $C = \mbox{COPY}(X)$ that will play itself with weight $v_1$ in any
equilibrium.  Create a node
$C_1$ with preference list $(X, C_1)$. $C_1$ will play itself with
weight $1-v_1$. Set the preference list for node $C$ to $(C_1,
C)$. $C$ will play $C_1$ with weight $1 - v_1$, leaving weight $v_1$
on $C$.
%\\ 
%\BfPara{$\mbox{DOUBLE}(X)$}
\subsubsection*{$\mbox{DOUBLE}(X)$}
We can add
a new node $M = \mbox{DOUBLE}(X)$ that
will play itself with weight $\min(1, v_1 * 2)$ in any equilibrium.  Create
player $M_1 = \mbox{COPY}(X)$ and set $M$ as $\mbox{SUM}(X,M_1)$.
%\\ 
%\BfPara{$\mbox{LESS}(X,Y)$}
\subsubsection*{$\mbox{LESS}(X,Y)$}
Given $\epsilon_l$ $(0 < \epsilon_l
\leq \frac{1}{2}$), We can add a new node $L
= \mbox{LESS}(X,Y)$ to the game that in any equilibrium will play only
itself if $v_1 - v_2 \geq \epsilon_l$, and will play
 $L_1$ (for a new node $L_1$) if $v_1 \leq v_2$.  First
create $D = \mbox{DIFF}(X,Y)$.  Then create $M_1 = \mbox{DOUBLE}(D)$.
For $i=1$ to $-\log \epsilon_l$, create player $M_{i+1} =
\mbox{DOUBLE}(M_i)$.  Call the last DOUBLE player node $L$ and
the extra player for the sum player of the last DOUBLE player node
$L_1$.  If $v_1 \leq v_2$, the DIFF player will return 0, so player
$L$ will play the result of multiplying 0 by 2 many times, or 0. If
$v_1 - v_2 \geq \epsilon_l$, player $L$ will play the max of 1 and
$(v_1 - v_2) * 2^{- \log \epsilon_l} = (v_1 - v_2) *
\frac{1}{\epsilon_l} \geq
\frac{\epsilon_l}{\epsilon_l} = 1$.
%\\
%\BfPara{$\mbox{HALF}(X)$}
\subsubsection*{$\mbox{HALF}(X)$}
We can add
a new node $H = \mbox{HALF}(X)$ that will play itself with weight $v_1/2$ in any equilibrium.  Create a node $H_1$ with
preference list $(X, H_1)$. $H_1$ will play itself with weight $1 -
v_1$. Then create two more nodes: $H_2$ and $H_3$. Node $H_2$ has
preference list $(H_1, H_3, H_2)$. Node $H_3$ has preference list
$(H_1, H, H_3)$. Set the preference list for node $H$ to be $(H_1,
H_2, H)$. Each of $H$, $H_2$, and $H_3$ will use its first choice with
weight $1 - v_1$, leaving $v_1$ for its other two choices.  Then, we
have $w_H(H) + w_H(H_2) = v_1$, $w_{H_2}(H_2) + w_{H_2}(H_3) = v_1$,
and $w_{H_3}(H_3) + w_{H_3}(H) = v_1$. In any equilibrium, it must be
true that $w_H(H_2) = w_{H_2}(H_2)$, $w_{H_2}(H_3) = w_{H_3}(H_3)$,
and $w_{H_3}(H) = w_H(H)$.  Solving this gives $w_H(H) = w_H(H_2) =
w_{H_2}(H_2) = w_{H_2}(H_3) = w_{H_3}(H_3) = w_{H_3}(H) =
\frac{v_1}{2}$.
\medskip

As in~\cite{DaskalakisGoldbergPapadimitriou06}, our LESS player plays
the specified action (itself, in our case) with weight 1 if $v_1 \geq
v_2 + \epsilon_l$, and plays itself with weight 0 if $v_1 \leq v_2$,
but will play some unspecified fraction on itself if $v_2 < v_1 < v_2
+ \epsilon_l$.  We use the LESS player to extract the bits
representing the coordinates of a cubelet to be passed into the
circuit.  This procedure is identical to that
of~\cite{DaskalakisGoldbergPapadimitriou06}.  Let $X$ denote the
$x$-coordinate player, and let $X_1 = \mbox{COPY}(X)$.  For $i$ from
$1$ through $n$, we create players $B_i = \mbox{LESS}(2^{-i},X_i)$ and
$X_{i+1} = \mbox{DIFF}(X_i, \mbox{HALF}^{i}(B_i))$, where
$\mbox{HALF}^i$ indicates applying the HALF gadget $i$ times. 
 It can be shown that as long as $x$ is not too close to a multiple
of $2^{-n}$, we will extract its $n$ bits correctly.  If this is not
the case, however, we will not properly extract the bits, and our
circuit simulation may return an arbitrary value.  We resolve this
problem using the same technique as
in~\cite{DaskalakisGoldbergPapadimitriou06}: we compute the circuit for
a large constant number of points surrounding the vertex and take the
average of the resulting vectors.  Since these details are almost
identical to that of~\cite[Lemma~4]{DaskalakisGoldbergPapadimitriou06},
we omit them.  